Neighborhood image processors are a class of devices that operate upon a first array or matrix of pixels to generate a second transformation matrix in which each pixel has a value depending upon its value in the original matrix and the values of its surrounding or neighboring pixels in the original matrix. These neighborhood processors are extremely useful devices and find particular utility for pattern recognition, image enhancement, area correlation, automatic inspection systems and other similar image processing functions.
In general, two diametrically opposite approaches have been taken to construct these special purpose neighborhood processors. One form is known as a parallel array processor in which there is a single computing element or module for each pixel. Parallel array neighborhood processors of this type are disclosed in U.S. Pat. No. 3,106,698 to Unger and various papers relating to the Illiac III pattern recognition computer. Generally, these parallel array processors comprise a matrix of identical processing modules, each module including a memory register for storing the value of a single pixel and a neighborhood logic translator for computing the transformed value of that pixel as a function of the present value of the pixel and its neighbhoring pixel values. Parallel connections are necessary between the translator for each module and all of the neighboring memory registers.
The principal advantage of these parallel array processors is speed. The transformation of the entire image matrix is performed substantially simultaneously. The principle disadvantage of the parallel array processor configuration is complexity since this construction requires one processing module for each pixel in the image matrix. In most practical applications the matrix size must be relatively large in order to achieve high resolution. For example, when the input matrix is generated by a state of the art television pick-up tube it may be digitized into a matrix of up to about 1,000.times.1,000 pixels. Accordingly, a parallel array processor would require one million relatively complex processing modules. The construction of such a parallel array processor is accordingly very costly.
A serial neighborhood processor represents an alternative approach to parallel array neighborhood processors. Examples of serial neighborhood processors are disclosed in U.S. Pat. No. 4,167,728 to Sternberg, U.S. Pat. No. 4,290,049 to Sternberg et al., and U.S. Pat. No. 178,312 to Sternberg et al. These patents and application are hereby incorporated by reference. Disclosed therein is a system which employs a chain or pipeline of individually programmable serial neighborhood transformation stages. Each stage is capable of generating the transformed value of one pixel within a single clock pulse interval. The output of each serial neighborhood transformation stage occurs at the same rate as its input. This allows the output of one stage to be provided to the input of a subsequent stage which may perform different neighborhood logic transformations. Each stage thus performs one transformation over the entire image in contrast with the parallel array processor technique which requires one processing stage for each pixel in the image. One of the tradeoffs, however, with the serial neighborhood processing approach is speed since each pixel and its neighbors must be sequentially presented to the neighborhood transformation logic circuit one at a time. Other examples of serial neighborhood processors are disclosed in U.S. Pat. No. 3,805,035 to Serra and in Kruse's article entitled "A Parallel Picture Processing Machine", IEEE Transactions on Computers, Vol. C-22, No. 12, Dec. 1973.
Sternberg, in his U.S. Pat. No. 4,174,514 (hereby incorporated by reference) and Kruse in his article recognize that the speed of serial neighborhood processors could be increased by partitioning the image matrix. In Sternberg's approach the image matrix is partitioned so that contiguous segments of the image could be processed simultaneously by two or more adjacent serial neighborhood processors. Sternberg also realized that provision had to be made in this partitioning scheme to bi-directionally transfer pixel data between adjacent serial neighborhood processors. This transfer becomes necessary when the neighboring pixels of the pixel being transformed in one processor is contained in the image matrix segment supplied to the other processor.